#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;



//method 1
void getNqueens(int level, vector<int> &pos, int &ans, vector<int> &a, vector<int> &b, vector<int> &c)
{
    if (level == pos.size()) {
        ans++;
        return;
    }

   for (int i = 0; i < pos.size(); i++) {
      if (a[i] || b[level+i] || c[level-i+pos.size()-1]) continue;
      a[i] = 1;
      b[level+i] = 1;
      c[level-i+pos.size()-1] = 1;
      pos[level] = i;
      getNqueens(level+1, pos, ans, a, b, c);
      a[i] = 0;
      b[level+i] = 0;
      c[level-i+pos.size()-1] = 0;
   }
}

class Solution {
    public:
        int totalNQueens(int n) {
            int ans = 0;                        
            vector<int> pos(n,0);
            vector<int> a(n, 0);
            vector<int> b(2*n-1, 0);
            vector<int> c(2*n-1, 0);
            getNqueens(0, pos, ans, a, b, c); 
            return ans;
        }
};

//add much better code
bool isValid(int id, int j, vector<int> &col)
{
    for (int i = 0; i < id; i++) {
        if (col[i] == j || abs(col[i] - j) == id - i) return false;
    }    
    return true;
}

void dfsQueue(int index, vector<int> &col , vector<string> &cur, vector<vector<string> > &ans)
{
    if (index == col.size()) {
        ans.push_back(cur);
        return;
    }    

    for (int i = 0; i < col.size(); i++) {
        if (isValid(index, i, col)) {
            col[index] = i; 
            cur[index][i] = 'Q'; 
            dfsQueue(index+1, col, cur, ans);
            cur[index][i] = '.'; 
        }    
    }    
}

    vector<vector<string> > solveNQueens(int n) { 
        vector<vector<string> > ans; 
       // return ans;
        vector<string> cur(n, string(n, '.')); 
        vector<int> col(n, 0);
        dfsQueue(0, col, cur, ans);
        return ans; 
    } 


//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    mySolution.solveNQueens(2);   
    return 0;
}
